import java.util.Scanner;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Admin
 * Date: 2022-11-30
 * Time: 20:35
 */
import java.util.*;

public class Demo2 {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        long[] arr = new long[100001];
        int index = -1;

        arr[1] = 1;
        arr[2] = 2;
        for(int i  = 3; i < 100001; i++) {
            arr[i] = arr[i - 1] + arr[i - 2];
            if(index == -1 && arr[i] > 1000000) {
                index = i;
            }
            arr[i] = arr[i] % 1000000;

        }

        while(scan.hasNextInt()) {
            int n = scan.nextInt();
            if(n < index) {
                System.out.printf("%d\n",arr[n]);
            }else {
                System.out.printf("%06d\n",arr[n]);
            }
        }
    }
}
